#!/usr/bin/env python3

"""
循环循环单链表
"""

class Node:

    def __init__(self, data):
        """
        初始化结点
        """
        self.data = data
        self.next = None


class CircularSingleLinkedList:

    def __init__(self):
        """
        初始化结点
        """
        self.head = Node(None)

    def CreateCircularSingleLinkedList(self):
        cNode = self.head
        ele = input("请输入结点的值: ")
        while ele != '#':
            self.InsertElementInHead(ele)
            ele = input("请输入结点的值: ")


    def GetLength(self):
        """
        获取循环循环单链表长度
        """
        node_len = 0
        cNode = self.head
        while cNode.next != self.head:
            node_len += 1
            cNode = cNode.next
        #  print("循环单链表长度为: %d" % node_len)
        return node_len


    def IsEmpty(self):
        """
        判断循环单链表是否为空
        """
        is_empty = True if self.GetLength() == 0 else False
        #  print("循环单链表是否为空: {0}".format(is_empty))
        return is_empty


    def InsertElementInTail(self):
        """
        O(n)
        """
        ele = input("请输入待插入(尾部插入)结点的值: ")
        if ele == '#':
            return
        cNode = self.head
        nNode = Node(int(ele))

        #  找到尾部位置
        while cNode.next != self.head:
            cNode = cNode.next
        #  插入结点
        cNode.next = nNode
        nNode.next = self.head


    def InsertElementInHead(self, ele=None):
        """
        O(1)
        """
        ele = input("请输入待插入(头部插入)结点的值: ") if ele is None else ele
        if ele == '#':
            return
        cNode = self.head
        nNode = Node(int(ele))

        #  插入结点
        nNode.next = cNode.next
        cNode.next = nNode


    def DeleteElement(self):
        ele = input("请输入待删除的值: ")


    def GetElement(self):
        """
        获取表中指定位置结点的值
        """
        pos = 0
        dpos = int(input("请输入链表中指定位置: "))
        cNode = self.head
        if self.IsEmpty():
            print("循环单链表为空")
            return
        if dpos > self.GetLength():
            print("不存在该位置")
            return
        while cNode.next != None:
            pos += 1
            cNode = cNode.next
            if pos == dpos:
                print("{0}位置值为: {1}".format(dpos, cNode.data))
                return cNode.data

    def FindElement(self):
        """
        在表中查找某一结点
        """
        pos = 0
        ele = int(input("请输入链表中待查找节点的值: "))
        cNode = self.head
        if self.IsEmpty():
            print("循环单链表为空")
            return
        while cNode.next != None and cNode.data != ele:
            cNode = cNode.next
            pos +=1
        if cNode.data == ele:
            print("查找到{0}元素的位置{1}".format(ele, pos))
        else:
            print("未找到%d元素" % ele)

    def VisitElement(self, tNode):
        """
        访问表中某一结点值
        """
        if tNode != None:
            print(tNode.data, "->", end=" ")
        else:
            print("None")

    def TravelElement(self):
        """
        遍历表中所有结点
        """
        print("开始遍历循环单链表...")
        if self.IsEmpty():
            print("循环单链表为空")
            return
        cNode = self.head
        while cNode.next != self.head:
            cNode = cNode.next
            self.VisitElement(cNode)



if __name__ == "__main__":
    csll_class = CircularSingleLinkedList()
    csll_class.CreateCircularSingleLinkedList()
    csll_class.TravelElement()
